import java.util.Stack;

public class demo {
    /**
     * 实现要求：
     * 1、根据已有的代码片段，创建二叉搜索树；
     * 2、用中序遍历输出排序结果，结果形如：0，1，2 ，3 ，4， 5， 6， 7， 8， 9，
     * 3、使用递归、非递归二种方式实现遍历；
     * 4、注意编写代码注释。
     */

    public static void main(String[] args) {

        final int[] values = { 1, 3, 4, 5, 2, 8, 6, 7, 9, 0 };

        System.out.println("Create BST: ");
        Node root = createBinaryTree(values);

        System.out.println("Traversing the BST with recursive algorithm: ");
        inOrderTransvalWithRecursive(root);

        System.out.println("");//为了好看添加这行

        System.out.println("Traversing the BST with iterative algorithm: ");
        inOrderTransvalWithIterate(root);
    }

    static int a = 0;//为了不变动createBinaryTree的参数，不得不添加这行

    // 构建二叉树
    public static Node createBinaryTree(int[] values) {
        // TODO:
        Node root = null;
        if(a>=values.length){
            root = null;
        }else{
            root = new Node(values[a]);
            a++;
            root.left = createBinaryTree(values);
            root.right = createBinaryTree(values);
        }
        return root;

    }

    // 递归实现
    public static void inOrderTransvalWithRecursive(Node node) {
        // TODO:
        if(node!=null){
            inOrderTransvalWithRecursive(node.left);
            System.out.print(node.data);
            inOrderTransvalWithRecursive(node.right);
        }
    }

    // 非递归实现
    public static void inOrderTransvalWithIterate(Node root) {
        // TODO:
        /*中序是左根右，有左就一路往左，根存进栈里。没左子树了出栈1个根，显示，然后往右走1步。右边如果也没有就再出栈1个根，再往右看看。*/

            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    //入栈
                    stack.push(root);
                    root = root.left;
                } else {
                    //出栈
                    root = stack.pop();
                    System.out.print(root.data);
                    root = root.right;
                }
            }

    }
}

class Node{
    Integer data=null;
    Node left;
    Node right;
    public Node(int in){
        data = in;
    }
}
